<!DOCTYPE html>
<!-- saved from url=(0063)https://hit-alibaba.github.io/interview/basic/algo/Sorting.html -->
<html lang=""><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
        
        
        <title>排序 · 笔试面试知识整理</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge">
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.2">
        
        
        
    
    <link rel="stylesheet" href="./排序 · 笔试面试知识整理_files/style.css">

    
            
                
                <link rel="stylesheet" href="./排序 · 笔试面试知识整理_files/plugin.css">
                
            
                
                <link rel="stylesheet" href="./排序 · 笔试面试知识整理_files/website.css">
                
            
                
                <link rel="stylesheet" href="./排序 · 笔试面试知识整理_files/search.css">
                
            
                
                <link rel="stylesheet" href="./排序 · 笔试面试知识整理_files/website(1).css">
                
            
        

    

    
        
    
        
    
        
    
        
    
        
    
        
    

        
    
    
    <meta name="HandheldFriendly" content="true">
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="https://hit-alibaba.github.io/interview/gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="https://hit-alibaba.github.io/interview/gitbook/images/favicon.ico" type="image/x-icon">

    
    
    
    
    
    

    <link rel="prev" href="https://hit-alibaba.github.io/interview/basic/algo/Hash-Table.html"></head>
    <body>
        
<div class="book without-animation with-summary font-size-2 font-family-1">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="Type to search">
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        
    
        <li class="chapter " data-level="1.1" data-path="../../">
            
                <a href="https://hit-alibaba.github.io/interview/">
            
                    
                    Introduction
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="../">
            
                <a href="https://hit-alibaba.github.io/interview/basic/">
            
                    
                    基础知识
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.2.1" data-path="../network/">
            
                <a href="https://hit-alibaba.github.io/interview/basic/network/">
            
                    
                    计算机网络
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.2.1.1" data-path="../network/HTTP.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/network/HTTP.html">
            
                    
                    HTTP 协议
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.1.2" data-path="../network/TCP.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/network/TCP.html">
            
                    
                    TCP 协议
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.1.3" data-path="../network/UDP.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/network/UDP.html">
            
                    
                    UDP 协议
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.1.4" data-path="../network/IP.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/network/IP.html">
            
                    
                    IP 协议
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.1.5" data-path="../network/Socket-Programming-Basic.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/network/Socket-Programming-Basic.html">
            
                    
                    Socket 编程
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.2.2" data-path="./">
            
                <a href="https://hit-alibaba.github.io/interview/basic/algo/">
            
                    
                    数据结构与算法
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.2.2.1" data-path="Linked-List.md">
            
                <span>
            
                    
                    链表
            
                
            

            
        </span></li>
    
        <li class="chapter " data-level="1.2.2.2" data-path="Tree.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/algo/Tree.html">
            
                    
                    树
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.2.3" data-path="Hash-Table.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/algo/Hash-Table.html">
            
                    
                    哈希表
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="1.2.2.4" data-path="Sorting.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html">
            
                    
                    排序
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.2.5">
            
                <span>
            
                    
                    搜索
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.2.6">
            
                <span>
            
                    
                    字符串
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.2.7">
            
                <span>
            
                    
                    向量/矩阵
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.2.8" data-path="Random.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/algo/Random.html">
            
                    
                    随机
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.2.9" data-path="Greedy.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/algo/Greedy.html">
            
                    
                    贪心
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.2.10" data-path="DP.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/algo/DP.html">
            
                    
                    动态规划
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.2.3" data-path="../arch/">
            
                <a href="https://hit-alibaba.github.io/interview/basic/arch/">
            
                    
                    体系结构与操作系统
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.2.3.1" data-path="../arch/Arch.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/arch/Arch.html">
            
                    
                    体系结构基础
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.3.2" data-path="../arch/OS.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/arch/OS.html">
            
                    
                    操作系统基础
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.3.3" data-path="../arch/Concurrency.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/arch/Concurrency.html">
            
                    
                    并发技术
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.3.4" data-path="../arch/Memory-Management.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/arch/Memory-Management.html">
            
                    
                    内存管理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.3.5" data-path="../arch/Disk-And-File.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/arch/Disk-And-File.html">
            
                    
                    磁盘与文件
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.2.4" data-path="../db/">
            
                <a href="https://hit-alibaba.github.io/interview/basic/db/">
            
                    
                    数据库系统
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.2.4.1" data-path="../db/Transaction.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/db/Transaction.html">
            
                    
                    事务处理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.4.2" data-path="../db/DB-Index.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/db/DB-Index.html">
            
                    
                    索引
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.2.5" data-path="../compiler/">
            
                <a href="https://hit-alibaba.github.io/interview/basic/compiler/">
            
                    
                    编译原理
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.2.5.1" data-path="../compiler/Compiler-Arch.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/compiler/Compiler-Arch.html">
            
                    
                    编译器架构
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.2.6" data-path="../design/">
            
                <a href="https://hit-alibaba.github.io/interview/basic/design/">
            
                    
                    设计模式
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.2.6.1" data-path="../design/OO-Basic.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/design/OO-Basic.html">
            
                    
                    面向对象基础
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.6.2" data-path="../design/GOP.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/design/GOP.html">
            
                    
                    四人帮设计模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.6.3" data-path="../design/MVC.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/design/MVC.html">
            
                    
                    MVC 与 MVVM
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.2.7" data-path="../scm/">
            
                <a href="https://hit-alibaba.github.io/interview/basic/scm/">
            
                    
                    版本控制
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.2.7.1" data-path="../scm/Git.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/scm/Git.html">
            
                    
                    Git
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2.7.2" data-path="../scm/SVN.html">
            
                <a href="https://hit-alibaba.github.io/interview/basic/scm/SVN.html">
            
                    
                    SVN
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../../iOS/">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/">
            
                    
                    iOS 开发
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.3.1" data-path="../../iOS/ObjC-Basic/">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/ObjC-Basic/">
            
                    
                    Objective-C 语言基础
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.3.1.1" data-path="../../iOS/ObjC-Basic/Class.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/ObjC-Basic/Class.html">
            
                    
                    类与对象
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.1.2" data-path="../../iOS/ObjC-Basic/Block.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/ObjC-Basic/Block.html">
            
                    
                    Block 编程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.1.3" data-path="../../iOS/ObjC-Basic/Runtime.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/ObjC-Basic/Runtime.html">
            
                    
                    Objective-C Runtime
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.1.4" data-path="../../iOS/ObjC-Basic/MM.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/ObjC-Basic/MM.html">
            
                    
                    Objective-C 内存管理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.1.5" data-path="../../iOS/ObjC-Basic/Runloop.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/ObjC-Basic/Runloop.html">
            
                    
                    Runloop
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.3.2" data-path="../../iOS/Cocoa-Touch/">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/">
            
                    
                    Cocoa Touch
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.3.2.1" data-path="../../iOS/Cocoa-Touch/Event-Handling.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/Event-Handling.html">
            
                    
                    事件处理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2.2" data-path="../../iOS/Cocoa-Touch/UIApplication.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/UIApplication.html">
            
                    
                    UIApplication
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2.3" data-path="../../iOS/Cocoa-Touch/UIView-Basic.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/UIView-Basic.html">
            
                    
                    UIView
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2.4" data-path="../../iOS/Cocoa-Touch/UIViewController.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/UIViewController.html">
            
                    
                    UIViewController
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2.5" data-path="../../iOS/Cocoa-Touch/Animation.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/Animation.html">
            
                    
                    动画
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2.6" data-path="../../iOS/Cocoa-Touch/Network.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/Network.html">
            
                    
                    网络编程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2.7" data-path="../../iOS/Cocoa-Touch/Multithreading.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/Multithreading.html">
            
                    
                    并发编程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2.8" data-path="../../iOS/Cocoa-Touch/File-System.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/File-System.html">
            
                    
                    文件系统
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2.9" data-path="../../iOS/Cocoa-Touch/Design.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/Design.html">
            
                    
                    设计模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.2.10" data-path="../../iOS/Cocoa-Touch/Performance.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Cocoa-Touch/Performance.html">
            
                    
                    性能
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.3.3" data-path="../../iOS/Swift/">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Swift/">
            
                    
                    Swift
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.3.3.1" data-path="../../iOS/Swift/Class.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Swift/Class.html">
            
                    
                    类与对象
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.3.2" data-path="../../iOS/Swift/Struct-And-Enum.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Swift/Struct-And-Enum.html">
            
                    
                    结构体与枚举
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.3.3" data-path="../../iOS/Swift/Function-And-Closure.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Swift/Function-And-Closure.html">
            
                    
                    函数与闭包
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.3.4" data-path="../../iOS/Questions.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/Questions.html">
            
                    
                    面试问题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3.5" data-path="../../iOS/More.html">
            
                <a href="https://hit-alibaba.github.io/interview/iOS/More.html">
            
                    
                    更多资料
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="../../Android/">
            
                <a href="https://hit-alibaba.github.io/interview/Android/">
            
                    
                    Android 开发
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.4.1" data-path="../../Android/Java/">
            
                <a href="https://hit-alibaba.github.io/interview/Android/Java/">
            
                    
                    Java 基础
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.4.1.1" data-path="../../Android/Java/Questions.html">
            
                <a href="https://hit-alibaba.github.io/interview/Android/Java/Questions.html">
            
                    
                    面试问题
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.4.2" data-path="../../Android/basic/">
            
                <a href="https://hit-alibaba.github.io/interview/Android/basic/">
            
                    
                    Android 基础
            
                </a>
            

            
            <ul class="articles">
                
    
        <li class="chapter " data-level="1.4.2.1" data-path="../../Android/basic/Android-Arch.html">
            
                <a href="https://hit-alibaba.github.io/interview/Android/basic/Android-Arch.html">
            
                    
                    Android 系统架构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4.2.2" data-path="../../Android/basic/Activity-Service-Lifecircle.html">
            
                <a href="https://hit-alibaba.github.io/interview/Android/basic/Activity-Service-Lifecircle.html">
            
                    
                    Activity/Service 生命周期
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4.2.3" data-path="../../Android/basic/Android-Animation.html">
            
                <a href="https://hit-alibaba.github.io/interview/Android/basic/Android-Animation.html">
            
                    
                    Android 中的动画(补帧与逐帧)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4.2.4" data-path="../../Android/basic/Android-LaunchMode.html">
            
                <a href="https://hit-alibaba.github.io/interview/Android/basic/Android-LaunchMode.html">
            
                    
                    Activity 的 4 种启动模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4.2.5" data-path="../../Android/basic/ListView-Optimize.html">
            
                <a href="https://hit-alibaba.github.io/interview/Android/basic/ListView-Optimize.html">
            
                    
                    ListView原理与优化
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4.2.6" data-path="../../Android/basic/Android-handler-thread-looper.html">
            
                <a href="https://hit-alibaba.github.io/interview/Android/basic/Android-handler-thread-looper.html">
            
                    
                    Android 中的 Thread, Looper 和 Handler 机制
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    
        <li class="chapter " data-level="1.4.3" data-path="../../Android/Questions.html">
            
                <a href="https://hit-alibaba.github.io/interview/Android/Questions.html">
            
                    
                    面试问题
            
                </a>
            

            
        </li>
    

            </ul>
            
        </li>
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com/" target="blank" class="gitbook-link">
            Published with GitBook
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <a class="btn pull-left js-toolbar-action" aria-label="" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#"><i class="fa fa-align-justify"></i></a><div class="dropdown pull-right js-toolbar-action"><a class="btn toggle-dropdown" aria-label="Share" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#"><i class="fa fa-share-alt"></i></a><div class="dropdown-menu dropdown-left"><div class="dropdown-caret"><span class="caret-outer"></span><span class="caret-inner"></span></div><div class="buttons"><button class="button size-5 ">Facebook</button><button class="button size-5 ">Google+</button><button class="button size-5 ">Twitter</button><button class="button size-5 ">Weibo</button><button class="button size-5 ">Instapaper</button></div></div></div><a class="btn pull-right js-toolbar-action" aria-label="" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#"><i class="fa fa-facebook"></i></a><a class="btn pull-right js-toolbar-action" aria-label="" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#"><i class="fa fa-twitter"></i></a><div class="dropdown pull-left font-settings js-toolbar-action"><a class="btn toggle-dropdown" aria-label="Font Settings" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#"><i class="fa fa-font"></i></a><div class="dropdown-menu dropdown-right"><div class="dropdown-caret"><span class="caret-outer"></span><span class="caret-inner"></span></div><div class="buttons"><button class="button size-2 font-reduce">A</button><button class="button size-2 font-enlarge">A</button></div><div class="buttons"><button class="button size-2 ">Serif</button><button class="button size-2 ">Sans</button></div><div class="buttons"><button class="button size-3 ">White</button><button class="button size-3 ">Sepia</button><button class="button size-3 ">Night</button></div></div></div><h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href="https://hit-alibaba.github.io/interview/">排序</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <h2 id="排序算法的评价"><a name="排序算法的评价" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#排序算法的评价"><i class="fa fa-link" aria-hidden="true"></i></a>排序算法的评价</h2>
<h4 id="稳定性"><a name="稳定性" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#稳定性"><i class="fa fa-link" aria-hidden="true"></i></a>稳定性</h4>
<p>稳定排序算法会依照相等的关键（换言之就是值）维持纪录的相对次序。也就是一个排序算法是稳定的，就是当有两个有相等关键的纪录R和S，且在原本的串行中R出现在S之前，在排序过的串行中R也将会是在S之前。</p>
<h4 id="计算复杂度（最差、平均、和最好表现）"><a name="计算复杂度（最差、平均、和最好表现）" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#计算复杂度（最差、平均、和最好表现）"><i class="fa fa-link" aria-hidden="true"></i></a>计算复杂度（最差、平均、和最好表现）</h4>
<p>依据串行（list）的大小（n），一般而言，好的表现是O(nlogn)，且坏的行为是O(n2)。对于一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(nlogn)。</p>
<p>所有基于比较的排序的时间复杂度至少是 O(nlogn)。</p>
<h2 id="常见排序算法"><a name="常见排序算法" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#常见排序算法"><i class="fa fa-link" aria-hidden="true"></i></a>常见排序算法</h2>
<h4 id="稳定排序："><a name="稳定排序：" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#稳定排序："><i class="fa fa-link" aria-hidden="true"></i></a>稳定排序：</h4>
<ul>
<li>冒泡排序（Bubble Sort） — O(n²)</li>
<li>插入排序（Insertion Sort）— O(n²)</li>
<li>桶排序（Bucket Sort）— O(n); 需要 O(k) 额外空间</li>
<li>计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间</li>
<li>合并排序（Merge Sort）— O(nlogn); 需要 O(n) 额外空间</li>
<li>二叉排序树排序 （Binary tree sort） — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间</li>
<li>基数排序（Radix sort）— O(n·k); 需要 O(n) 额外空间</li>
</ul>
<h4 id="不稳定排序"><a name="不稳定排序" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#不稳定排序"><i class="fa fa-link" aria-hidden="true"></i></a>不稳定排序</h4>
<ul>
<li>选择排序（Selection Sort）— O(n²)</li>
<li>希尔排序（Shell Sort）— O(nlogn)</li>
<li>堆排序（Heapsort）— O(nlogn)</li>
<li>快速排序（Quicksort）— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序</li>
</ul>
<h4 id="快排"><a name="快排" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#快排"><i class="fa fa-link" aria-hidden="true"></i></a>快排</h4>
<p>快排是经典的 divide &amp; conquer 问题，如下用于描述快排的思想、伪代码、代码、复杂度计算以及快排的变形。</p>
<h5 id="快排的思想"><a name="快排的思想" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#快排的思想"><i class="fa fa-link" aria-hidden="true"></i></a>快排的思想</h5>
<p>如下的三步用于描述快排的流程：</p>
<ul>
<li>在数组中随机取一个值作为标兵</li>
<li>对标兵左、右的区间进行划分(将比标兵大的数放在标兵的右面，比标兵小的数放在标兵的左面，如果倒序就反过来)</li>
<li>重复如上两个过程，直到选取了所有的标兵并划分(此时每个标兵决定的区间中只有一个值，故有序)</li>
</ul>
<h5 id="伪代码"><a name="伪代码" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#伪代码"><i class="fa fa-link" aria-hidden="true"></i></a>伪代码</h5>
<p>如下是快排的主体伪代码</p>
<pre><code>QUCIKSORT(A, p, r)
if p &lt; r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q-1)
    QUICKSORT(A, q+1, r)
</code></pre><p>如下是用于选取标兵以及划分的伪代码</p>
<pre><code>PARTITION(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] &lt;= x
        i++
        swap A[i] with A[j]
swap A[i+1] with A[j]
return i+1
</code></pre><h5 id="代码"><a name="代码" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#代码"><i class="fa fa-link" aria-hidden="true"></i></a>代码</h5>
<pre><code class="lang-Swift"><span class="hljs-function"><span class="hljs-keyword">func</span> <span class="hljs-title">quickSort</span><span class="hljs-params">(<span class="hljs-keyword">inout</span> targetArray: [Int], begin: Int, end: Int)</span></span> {
    <span class="hljs-keyword">if</span> begin &lt; end {
        <span class="hljs-keyword">let</span> pivot = <span class="hljs-built_in">partition</span>(&amp;targetArray, begin: begin, end: end)
        <span class="hljs-built_in">quickSort</span>(&amp;targetArray, begin: begin, end: pivot - <span class="hljs-number">1</span>)
        <span class="hljs-built_in">quickSort</span>(&amp;targetArray, begin: pivot + <span class="hljs-number">1</span>, end: end)
    }
}

<span class="hljs-function"><span class="hljs-keyword">func</span> <span class="hljs-title">partition</span><span class="hljs-params">(<span class="hljs-keyword">inout</span> targetArray: [Int], begin: Int, end: Int)</span></span> -&gt; <span class="hljs-type">Int</span> {
    <span class="hljs-keyword">let</span> value = targetArray[end]
    <span class="hljs-keyword">var</span> i = begin - <span class="hljs-number">1</span>
    <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> begin ..&lt; end {
        <span class="hljs-keyword">if</span>  targetArray[j] &lt;= value {
            i += <span class="hljs-number">1</span>;
            swapTwoValue(&amp;targetArray[i], b: &amp;targetArray[j])
        }
    }
    swapTwoValue(&amp;targetArray[i+<span class="hljs-number">1</span>], b: &amp;targetArray[end])
    <span class="hljs-keyword">return</span> i+<span class="hljs-number">1</span>
}

<span class="hljs-function"><span class="hljs-keyword">func</span> <span class="hljs-title">swapTwoValue</span><span class="hljs-params">(<span class="hljs-keyword">inout</span> a: Int, <span class="hljs-keyword">inout</span> b: Int)</span></span> {
    <span class="hljs-keyword">let</span> <span class="hljs-built_in">c</span> = a
    a = b
    b = <span class="hljs-built_in">c</span>
}

<span class="hljs-keyword">var</span> testArray :[<span class="hljs-type">Int</span>] = [<span class="hljs-number">123</span>,<span class="hljs-number">3333</span>,<span class="hljs-number">223</span>,<span class="hljs-number">231</span>,<span class="hljs-number">3121</span>,<span class="hljs-number">245</span>,<span class="hljs-number">1123</span>]

<span class="hljs-built_in">quickSort</span>(&amp;testArray, begin: <span class="hljs-number">0</span>, end: testArray.<span class="hljs-built_in">count</span>-<span class="hljs-number">1</span>)
</code></pre>
<h5 id="复杂度分析"><a name="复杂度分析" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#复杂度分析"><i class="fa fa-link" aria-hidden="true"></i></a>复杂度分析</h5>
<p>在最好的情况下，每次 partition 都会把数组一分为二，所以时间复杂度 T(n) = 2T(n/2) + O(n)</p>
<p>解为 T(n) = O(nlog(n))</p>
<p>在最坏的情况下，数组刚好和想要的结果顺序相同，每次 partition 到的都是当前无序区中最小(或最大)的记录，因此只得到一个比上一次划分少一个记录的子序列。T(n) = O(n) + T(n-1)</p>
<p>解为 T(n) = O(n²)</p>
<p>在平均的情况下，快排的时间复杂度是 O(nlog(n))</p>
<h5 id="变形"><a name="变形" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#变形"><i class="fa fa-link" aria-hidden="true"></i></a>变形</h5>
<p>可以利用快排的 PARTITION 思想求数组中第K大元素这样的问题，步骤如下：</p>
<ul>
<li>在数组中随机取一个值作为标兵，左右分化后其顺序为X</li>
<li>如果 X == Kth 说明这就是第 K 大的数</li>
<li>如果 X &gt; Kth 说明第 K 大的数在标兵左边，继续在左边寻找第 Kth 大的数</li>
<li>如果 X &lt; Kth 说明第 K 大的数在标兵右边，继续在右边需找第 Kth - X 大的数</li>
</ul>
<p>这个问题的时间复杂度是 O(n)</p>
<p>T(n) = n + n/2 + n/4 + ... = O(n)</p>
<h3 id="参考资料"><a name="参考资料" class="plugin-anchor" href="https://hit-alibaba.github.io/interview/basic/algo/Sorting.html#参考资料"><i class="fa fa-link" aria-hidden="true"></i></a>参考资料</h3>
<ol>
<li><a href="http://blog.sina.com.cn/s/blog_4080505a0101iewt.html" target="_blank">各种基本排序算法的总结</a></li>
<li><a href="http://blog.csdn.net/whuslei/article/details/6442755" target="_blank">常用排序算法小结</a></li>
<li><a href="http://blog.csdn.net/yexinghai/article/details/4649923" target="_blank">八大排序算法总结</a></li>
<li><a href="https://en.wikipedia.org/wiki/Quicksort" target="_blank">QuickSort</a></li>
</ol>

                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class="search-results-count"></span> results matching "<span class="search-query"></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class="search-query"></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="https://hit-alibaba.github.io/interview/basic/algo/Hash-Table.html" class="navigation navigation-prev navigation-unique" aria-label="Previous page: 哈希表">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"排序","level":"1.2.2.4","depth":3,"next":{"title":"搜索","level":"1.2.2.5","depth":3,"ref":"","articles":[]},"previous":{"title":"哈希表","level":"1.2.2.3","depth":3,"path":"basic/algo/Hash-Table.md","ref":"basic/algo/Hash-Table.md","articles":[]},"dir":"ltr"},"config":{"plugins":["anchors"],"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"pluginsConfig":{"anchors":{},"highlight":{},"search":{},"lunr":{"maxIndexSize":1000000,"ignoreSpecialCharacters":false},"sharing":{"facebook":true,"twitter":true,"google":false,"weibo":false,"instapaper":false,"vk":false,"all":["facebook","google","twitter","weibo","instapaper"]},"fontsettings":{"theme":"white","family":"sans","size":2},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false}},"theme":"default","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"笔试面试知识整理","gitbook":"*","description":"一些 IT 笔试面试有关知识的整理，包括基础知识，安卓，iOS 开发等，希望对大家有所帮助"},"file":{"path":"basic/algo/Sorting.md","mtime":"2017-05-07T12:13:01.000Z","type":"markdown"},"gitbook":{"version":"3.2.2","time":"2017-07-16T04:50:11.921Z"},"basePath":"../..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="./排序 · 笔试面试知识整理_files/gitbook.js"></script>
    <script src="./排序 · 笔试面试知识整理_files/theme.js"></script>
    
        
        <script src="./排序 · 笔试面试知识整理_files/search-engine.js"></script>
        
    
        
        <script src="./排序 · 笔试面试知识整理_files/search.js"></script>
        
    
        
        <script src="./排序 · 笔试面试知识整理_files/lunr.min.js"></script>
        
    
        
        <script src="./排序 · 笔试面试知识整理_files/search-lunr.js"></script>
        
    
        
        <script src="./排序 · 笔试面试知识整理_files/buttons.js"></script>
        
    
        
        <script src="./排序 · 笔试面试知识整理_files/fontsettings.js"></script>
        
    

    


</body></html>